/*
 * @lc app=leetcode.cn id=919 lang=cpp
 *
 * [919] 完全二叉树插入器
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class CBTInserter {
private:
    TreeNode *root;
    vector<TreeNode *> candidate;

public:
    void getCandidate(TreeNode *root) {
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            TreeNode *node = que.front();
            que.pop();
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
            if (!node->right) {
                candidate.push_back(node);
            }
        }
    }
    CBTInserter(TreeNode *root) {
        this->root = root;
        this->getCandidate(root);
    }

    int insert(int val) {
        TreeNode *child = new TreeNode(val);
        TreeNode *parent = candidate.front();
        if (!parent->left) {
            parent->left = child;
        } else {
            parent->right = child;
            this->candidate.erase(this->candidate.begin());
        }
        this->candidate.push_back(child);
        return parent->val;
    }

    TreeNode *get_root() { return this->root; }
};

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter* obj = new CBTInserter(root);
 * int param_1 = obj->insert(val);
 * TreeNode* param_2 = obj->get_root();
 */
// @lc code=end
